/**
 * LeetCode111：二叉树的最小深度
 * 给定一个二叉树，找出其最小深度
 */

function TreeNode(val){
    this.val = val;
    this.left = this.right = null;
}

/**
 * @description 广度优先遍历，对每一个节点，赋予其层级，遍历到叶子节点时，停止遍历并返回层级
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root){
    if (!root) return 0;
    const q = [[root,1]];
    while(q.length){
        const [n,l] = q.shift();
        if (!n.left && !n.right){
            return l;
        }
        if (n.left){ q.push([n.left,l + 1]);}
        if (n.right){ q.push([n.right,l + 1]);}
    }
}

//时间复杂度：O(n)
//空间复杂度：O(n)